package com.xiyou.leetcode;

/**
 * 分发糖果问题：----- 贪心算法
 *
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 *
 */
public class CandyDistribution {

    /**
     * 糖果分发问题:
     * 1. 左边遍历: ratings[i] > ratings[i-1] 则 i 比 i-1 多 右边分比左边分数高，则右边的人糖果多
     * 2. 右边遍历: ratings[i] > ratings[i+1] 则 i 比 i+1 多 左边的分数高于右边的分数，则左边的人糖果多
     *
     * 满足左规则或者右规则的时候，注意 这里是或者，两者满足一个就行，满足之后最少需要被分得的糖果数量 就是我们说的最少糖果
     * 每个人最终分得的糖果数量就是这两个数量的最大值
     *
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        // 定义一个数组用来临时存储分配的值
        int[] left = new int[ratings.length];
        // 左边遍历
        for (int i = 0; i < ratings.length; i++) {
            if (i > 0 && ratings[i] > ratings[i-1]) {
                // 比左边的要多一个
                left[i] = left[i-1] + 1;
            } else {
                // 刚开始下标为0 或者 右边比左边的小就直接赋值为1
                left[i] = 1;
            }
        }

        // 循环遍历结束之后，我们就给left数组已经左遍历结束 已经有一版了
        // 从右边遍历 目的就是找到最小的
        // 表示糖果数
        int ret = 0;
        // 用来记录右边的糖果数
        int right = 0;
        for (int i = ratings.length - 1; i >= 0; i--) {
            // 最后的下标开始遍历
            if (i < ratings.length - 1  && ratings[i] > ratings[i+1]) {
                // 这时候 i 的糖 要比 i+1多
                right ++;
            } else {
                right = 1;
            }
            // 找到最大的就是两边都满足的
            ret += Math.max(left[i], right);
        }
        return ret;
    }


    /**
     * 常数遍历法
     *
     * @param ratings
     * @return
     */
    public int candy2(int[] ratings) {
        // 用来定义需要的糖果数
        int ret = 1;
        return ret;
    }
}
